//
//  main.c
//  006--字符串编码问题
//
//  Created by Shawn Li on 2020/5/12.
//  Copyright © 2020 Shawn. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


/*
题目: 字符串编码LeetCode-中等
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
例如:
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

*/

char * decodeString(char *s){
    int len = (int)strlen(s);
    int stackSize = 50;
    char *stack = (char*)malloc(stackSize *sizeof(char));
    
    int top = -1;
    
//    遍历输入字符，将‘]’之前的字符全部入栈。
    for (int i = 0; i < len; ++i) {
        if (s[i] != ']') {
//            如果超容了，就扩容。
            if (top == stackSize - 1) {
                stack = realloc(stack, (stackSize+=50) * sizeof(char));
            }
            stack[++top] = s[i];
        }else{
            int tempSize = 10;
//            这是一个新的栈用来保存需要重复的目标字符串
            char *temp = (char *)malloc(sizeof(char) * tempSize);
            
//            目标字符串暂存栈的栈顶
            int top_temp = -1;
            
//            相当于截取了'['和']'之间的字符（也就是需要重复的目标字符）全部存放在了 temp 这个栈里面。
            while (stack[top] != '[') {
                temp[++top_temp] = stack[top--];
            }
            
            char str_int[11];
//            这是记录了数字字符结束的下标
            int curTop = top;
            top--;
//            把是数字的字符的 下标起始 找到，其实这个时候字符里应该只有数字字符了。
            while (top != -1 && stack[top] >= '0' && stack[top] <= '9') {
                top--;
            }
            
//            把数字提出来
            for (int j = top + 1; j < curTop; ++j){
                str_int[j - (top + 1)] = stack[j];
            }
            //为字符串strOfInt数组加一个字符结束后缀'\0'，因为这个数组有 11 位，所以你要标志它的尾。
            str_int[curTop - (top + 1)] = '\0';
            
//            转成数字
            int curNum = atoi(str_int);
            
//            这个地方把原来的 stack 内容重置了，最后的结果就放在这里
            for (int k = 0; k < curNum; ++k) {
                
                int kk = top_temp;
                while (kk != -1) {
                    ++top;
                    stack[top] = temp[kk];
                    kk--;
                }
            }
            free(temp);
            temp = NULL;
        }
    }
    
    //realloc 动态内存调整;
    //void *realloc(void *mem_address, unsigned int newsize);
    //构成字符串stack后, 在stack的空间扩容.
    
    char *res = realloc(stack, (top + 1) * sizeof(char));
    
    res[++top] = '\0';
    
    free(stack);
    return res;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    // insert code here...
    printf("字符串编码问题!\n");
    
    char *s ;
    s = decodeString("12[a]");
    printf("字符编码后的结果: %s\n\n\n\n",s);
    
    s = decodeString("3[a]2[bc]");
    printf("字符编码后的结果: %s\n\n\n\n",s);

    s = decodeString("3[a2[c]]");
    printf("字符编码后的结果: %s\n\n\n\n",s);

    s = decodeString("2[abc]3[cd]ef");
    printf("字符编码后的结果: %s\n\n\n\n",s);

    printf("\n");
    
    return 0;
}
